﻿// 0814train04.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <queue>

using namespace std;

/*
 示例1
 grid = [[2,1,1],[1,1,0],[0,1,1]]
 输出
 4
 */

int orangesRotting(vector<vector<int>>& grid) {

    //1checked_grid 2双重循环，grid[r][c]==2加入队列，记录grid[r][c]==1
    //level++ for循环遍历queue, q.size() i<q.size() pop()
    //1无越界2grid[r][c]==1 3未访问 加入队列,fresh_num--

    int row_size = grid.size();
    int col_size = grid[0].size();

    int level = 0, fresh_num = 0;
    vector<bool>checked_status(col_size, false);
    vector<vector<bool>>checked_grid(row_size, checked_status);

    queue<pair<int,int>>oh_queue;
    for (int r=0; r<row_size; r++)
    {
        for (int c=0; c<col_size; c++)
        {
            if (grid[r][c]==2)
            {
                oh_queue.push(make_pair(r, c));
            }
            else if (grid[r][c]==1)
            {
                fresh_num++;
            }
        }
    }

    if (fresh_num == 0) return 0;

    vector<vector<int>>Direction = {{-1,0},{1,0},{0,-1},{0,1}};
    
    while (!oh_queue.empty())
    {
        level++;
        int q_size = oh_queue.size();

        for (int i = 0; i < q_size; i++)
        {
            pair<int, int>curr_node = oh_queue.front();
            oh_queue.pop();

            for (auto& dir_vec : Direction)
            {
                int curr_r = curr_node.first + dir_vec[0];
                int curr_c = curr_node.second + dir_vec[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r && is_curr_c)
                {
                    //未访问，可到达
                    bool is_visited = checked_grid[curr_r][curr_c];
                    bool is_available = grid[curr_r][curr_c] == 1;

                    if (!is_visited && is_available)
                    {
                        //标为已访问
                        checked_grid[curr_r][curr_c] = true;
                        oh_queue.push(make_pair(curr_r, curr_c));
                        fresh_num--;
                    }
                }


                //for------
            }


            //for-----
        }

        //while------
    }

    if (fresh_num != 0) return -1;

    return level - 1;
    //orangesRotting
}

/*
 假设将火星待改造的区域为 row * column 的网格，
 每个网格有 3 个值，宜居区、可改造区、死亡区，
 使用 YES、NO、NA 代替：
- YES 表示该网格已经完成大气改造；
- NO 表示该网格未进行改造，后期可进行改造；
- NA 表示死亡区，不作为判断是否改造完成的宜居，无法穿过；
初始化下，该区域可能存在多个宜居区，并且每个宜居区能同时在每个太阳日单位向上下左右四个方向的相邻格子进行扩散，自动将 4 个方向相邻的真空区改造成宜居区；
请计算这个待改造区域的网格中，可改造区是否能全部变成宜居区，如果可以，则返回改造的太阳日天数，不可以则返回-1。

输入
YES YES NO
NO NO NO
YES NO NO
输出
2

 */
void solve02(vector<vector<int>>&grid)
{
    //checked_grid oh_queue DirectionGrid
    int row_size = grid.size();
    int col_size = grid[0].size();

    vector<bool>checked_status(col_size, false);
    vector<vector<bool>>checked_grid(row_size, checked_status);

    queue<pair<int, int>>oh_queue;

    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,-1},{0,1}};

    int need_level = 0, changed_num = 0;

    //双重循环，统计grid[r][c]==2入队列，grid[r][c]==1
    for (int r=0;r<row_size; r++)
    {
	    for (int c=0; c<col_size; c++)
	    {
            if (grid[r][c]==2)
            {
                oh_queue.push(make_pair(r, c));
            }
            else if (grid[r][c]==1)
            {
                changed_num++;
            }

	    }
    }
    if (oh_queue.empty())
    {
        cout << -1;
        return;
    }

    if (changed_num == 0)
    {
        cout << 0;
        return;
    }

    while (!oh_queue.empty())
    {
        need_level++;
        //q_size 遍历queue出栈入栈
        int q_size = oh_queue.size();

        for (int i=0; i<q_size; i++)
        {
            //出栈
            pair<int, int>top_node = oh_queue.front();
            oh_queue.pop();

            //遍历DirectionGrid
            for (auto&dir_vec: DirectionGrid)
            {
                //3条件 1不越界 2可到达 3未访问
                int curr_r = top_node.first + dir_vec[0];
                int curr_c = top_node.second + dir_vec[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r&&is_curr_c)
                {
                    bool is_visited = checked_grid[curr_r][curr_c];
                    bool is_available = grid[curr_r][curr_c] == 1;

                    if (!is_visited&&is_available)
                    {
                        //标记，入队，changed_num--
                        checked_grid[curr_r][curr_c] = true;
                        oh_queue.push(make_pair(curr_r, curr_c));
                        changed_num--;
                    }

                }

                //forDirectionGrid
            }


            //for q_size------
        }


        //while (!oh_queue.empty())
    }

    if (changed_num!=0)
    {
        cout << -1;
        return;
    }
    cout << need_level - 1;
	//solve02
}


/*
 在选修某些课程之前需要一些先修课程。
 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，
 表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false
示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

prerequisites = [[1,0],[2,0]]
0->1 0->2
 */
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
    //touched_map记录int所有的指向
    unordered_map<int,vector<int>>touched_map;
    vector<int>in_vec(numCourses);

    for (auto&require_vec: prerequisites)
    {
        int arrive_node = require_vec[0];
        int start_node = require_vec[1];

        touched_map[start_node].push_back(arrive_node);
        //start_node->arrive_node arrive_node入度加1
        in_vec[arrive_node]++;
    }

    //for (auto&map_item:touched_map)
    //{
    //    cout << map_item.first << ' ';
	   // for (auto&num:map_item.second)
	   // {
    //        cout << num << ' ';
	   // }
    //    cout << '\n';
    //}
    queue<int>bfs_queue;
    for (int node=0; node<in_vec.size(); node++)
    {
        //入度为0，加入queue
        if (in_vec[node]==0)
        {
            bfs_queue.push(node);
        }
    }

    if (bfs_queue.empty()) return false;

    while (!bfs_queue.empty())
    {
        int top_node = bfs_queue.front();
        bfs_queue.pop();

        //遍历touched_vec，touched入度-1
        vector<int>touched_vec = touched_map[top_node];
        for (auto&touched_node:touched_vec)
        {
            in_vec[touched_node]--;
            if (in_vec[touched_node]==0)
            {
                bfs_queue.push(touched_node);
            }
        }
	    //while (!bfs_queue.empty())
    }


    for (auto&node_degree:in_vec)
    {
	    if (node_degree!=0)
	    {
            return false;
	    }
    }

    return true;
    //canFinish
}


/*
 输入描述
第一行是任务数 taskNum，第二行是任务的依赖关系数 relationsNum
接下来 relationsNum 行，每行包含两个 id，描述一个依赖关系，格式为：IDi IDj，
表示部署任务 i 部署完成了，部署任务 j 才能部署，IDi 和 IDj 值的范围为：[0, taskNum)
注：输入保证部署任务之间的依赖不会存在环。
输出描述
一个整数，表示一个站点的最短开站时间。i->j

输入
5
5
0 4
1 2
1 3
2 3
2 4

输出
3
 */
void solve03(int total_count, vector<vector<int>>&require_grid)
{
    //require_map, indegree_vec, bfs_queue
    //遍历require_grid，更新indegree
    //degree==0,bfs_queue.push
    unordered_map<int, vector<int>>require_map;

    vector<int>indegree_vec(total_count);

    queue<int>bfs_queue;

    for (auto&require_vec:require_grid)
    {
        int start_node = require_vec[0];
        int arrive_node = require_vec[1];

        require_map[start_node].push_back(arrive_node);

        //start->arrive, arrive入度+1
        indegree_vec[arrive_node]++;
        //for------
    }

    //for (auto&map_item: require_map)
    //{
    //    cout << map_item.first << ": ";
    //    for (auto&num:map_item.second)
    //    {
    //        cout << num << ' ';
    //    }
    //    cout << '\n';
    //}

    //degree==0,bfs_queue.push
    for (int node=0; node< total_count; node++)
    {
        if (indegree_vec[node]==0)
        {
            bfs_queue.push(node);
        }
    }

    if (bfs_queue.empty())
    {
        cout << 0;
        return;
    }

    int need_level = 0;
    while (!bfs_queue.empty())
    {
        need_level++;
        int q_size = bfs_queue.size();

        for (int i=0; i<q_size; i++)
        {
            int top_node = bfs_queue.front();
            bfs_queue.pop();

            vector<int>require_vec = require_map[top_node];

            for (auto& touched_node : require_vec)
            {
                indegree_vec[touched_node]--;
                if (indegree_vec[touched_node] == 0)
                {
                    bfs_queue.push(touched_node);
                }
            }
        }

        //while----
    }

    cout << need_level;
	//solve03------
}



int main()
{
    /*
	0 4
	1 2
	1 3
	2 3
	2 4
	*/
	{
        int total_count, grid_size;
        cin >> total_count >> grid_size;

        int col_size = 2;
        vector<vector<int>>require_grid(grid_size, vector<int>(col_size));

        for (int r=0; r<grid_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> require_grid[r][c];
            }
        }
        //vector<vector<int>>require_grid = { {0,4},{1,2},{1,3},{2,3},{2,4} };
        //int total_count = 5;
        solve03(total_count, require_grid);

        return 0;
	}

	{
        //prerequisites = [[1,0],[2,0]]
        int numCourses = 3;
        vector<vector<int>>prerequisites = { {1,0},{2,0},{0,1}};
        cout << canFinish(numCourses, prerequisites);

        return 0;
	}

    /*
    YES YES NO
	NO NO NO
	YES NO NO
     */
	{
        //vector<int>vec1 = { 2,2,1 };
        //vector<int>vec2 = { 1,1,1 };
        //vector<int>vec3 = { 2,1,1 };
        //vector<vector<int>>grid = { vec1 ,vec2,vec3 };
        vector<vector<int>>grid;
        string input;
        while (getline(cin,input))
        {
            if (input.empty()) break;
            vector<int>row_vec;
            stringstream oh_sstream(input);
            string token;
            while (oh_sstream>>token)
            {
                if (token=="YES")
                {
                    row_vec.push_back(2);
                }
            	else if (token=="NO")
                {
                    row_vec.push_back(1);
                }
                else if (token=="NA")
                {
                    row_vec.push_back(0);
                }
            }
            grid.push_back(row_vec);
        }

        solve02(grid);

        return 0;
	}


    //grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
    vector<vector<int>>grid = { {2, 1, 1},{1, 1, 0},{0, 1, 1} };
    cout << orangesRotting(grid);

    //main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
